package cn.yemuysy.code.check.service.impl;

import cn.yemuysy.code.check.model.InfringingWord;
import cn.yemuysy.code.check.model.InfringingWordMatch;
import lombok.Getter;

import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.concurrent.locks.ReentrantReadWriteLock;

/**
 * 管理单棵Trie树（Aho-Corasick自动机）的类。
 * <p>
 * 此类封装了与单棵Trie树相关的所有状态和操作，包括：
 * <ul>
 *     <li>词汇的添加</li>
 *     <li>失败链接（Failure Links）的构建</li>
 *     <li>文本匹配</li>
 *     <li>与其他TrieManager的合并</li>
 * </ul>
 * 所有需要锁保护的操作都使用传入的共享锁来确保线程安全。
 * </p>
 */
public class TrieManager {

    /**
     * Trie树的根节点。
     * 所有操作都从这个根节点开始。
     */
    @Getter
    private TrieNode root = new TrieNode();

    /**
     * 标志，指示失败链接是否已经构建。
     * 使用volatile确保多线程环境下的可见性。
     */
    private volatile boolean failureLinksBuilt = false;

    /**
     * 指示此Trie是否区分大小写。
     * 如果为true，则"Word"和"word"被视为不同的词；
     * 如果为false，则它们被视为相同的词。
     */
    private final boolean caseSensitive;

    /**
     * 用于保证线程安全的读写锁。
     * 此锁由外部传入，以便在多个TrieManager实例之间协调锁定。
     */
    private final ReentrantReadWriteLock lock;

    /**
     * 构造一个新的TrieManager。
     *
     * @param caseSensitive 指定此TrieManager管理的树是否区分大小写
     * @param lock          一个共享的读写锁，用于保证跨多个TrieManager操作的线程安全
     */
    public TrieManager(boolean caseSensitive, ReentrantReadWriteLock lock) {
        this.caseSensitive = caseSensitive;
        this.lock = lock;
    }

    /**
     * 向此Trie树中添加一个侵权词。
     * 添加后，失败链接状态会被重置为"未构建"。
     *
     * @param infringingWord 要添加的侵权词
     */
    public void addWord(InfringingWord infringingWord) {
        String wordToAdd = caseSensitive ? infringingWord.getWord() : infringingWord.getWord().toLowerCase();
        addWordToTrie(root, wordToAdd, infringingWord);
        failureLinksBuilt = false;
    }

    /**
     * 确保此Trie树的失败链接已经构建。
     * 采用双重检查锁定模式（Double-Checked Locking）来提高性能，
     * 避免在链接已构建的情况下进入重量级的写锁。
     */
    public void ensureFailureLinksBuilt() {
        if (!failureLinksBuilt) {
            lock.writeLock().lock();
            try {
                if (!failureLinksBuilt) {
                    buildFailureAndOutputLinks();
                    failureLinksBuilt = true;
                }
            } finally {
                lock.writeLock().unlock();
            }
        }
    }

    /**
     * 在给定的文本中查找所有匹配的侵权词。
     * 此方法首先确保失败链接已构建，然后使用Aho-Corasick算法在文本中查找所有匹配项。
     * 匹配过程会考虑站点适用性，只返回适用于指定站点的匹配结果。
     * 如果是不区分大小写的Trie，会自动处理大小写差异。
     *
     * @param text 要检查的文本
     * @param site 当前的站点上下文（可以为null表示所有站点）
     * @return 匹配结果列表，每个匹配包含位置、原始文本和侵权词信息
     */
    public List<InfringingWordMatch> findMatches(String text, String site) {
        ensureFailureLinksBuilt();
        List<InfringingWordMatch> matches = new LinkedList<>();
        findMatchesInText(text, site, matches);
        return matches;
    }

    /**
     * 清空此Trie树中的所有数据，并重置状态。
     * 此方法会创建一个全新的根节点，丢弃所有现有的节点和链接，
     * 并将失败链接构建状态重置为未构建。
     * 通常在合并操作后调用此方法来清空增量Trie，或者在需要完全重建Trie时使用。
     */
    public void clear() {
        root = new TrieNode();
        failureLinksBuilt = false;
    }

    /**
     * 从另一个TrieManager合并所有词汇到当前实例中。
     * 此方法将源TrieManager中的所有单词及其元数据复制到当前TrieManager中，
     * 保留所有单词的结束标记和侵权词信息。合并过程使用迭代方式进行，
     * 以避免大型Trie合并时可能的栈溢出问题。
     * 
     * 合并后，当前TrieManager的失败链接状态会被重置为未构建，
     * 需要调用{@link #ensureFailureLinksBuilt()}重新构建失败链接。
     *
     * @param other 要从中合并数据的TrieManager
     */
    public void mergeFrom(TrieManager other) {
        mergeTries(other.root, this.root);
        this.failureLinksBuilt = false; // 合并后需要重建
    }

    /**
     * 将一个单词及其元数据添加到Trie树中。
     * 遍历单词的每个字符，在Trie中创建相应的路径，并在最后一个节点设置单词结束标记。
     *
     * @param node 开始添加的节点，通常是根节点
     * @param word 要添加的单词文本
     * @param infringingWord 包含单词元数据的侵权词对象
     */
    private void addWordToTrie(TrieNode node, String word, InfringingWord infringingWord) {
        for (char c : word.toCharArray()) {
            node = node.getOrCreateChild(c);
        }
        node.setEndOfWord(infringingWord);
    }

    /**
     * 使用广度优先搜索（BFS）构建失败链接和输出链接。
     * 失败链接是Aho-Corasick算法的核心部分，它们指向在当前匹配失败时应该转移到的下一个状态。
     * 输出链接用于快速识别所有在当前节点结束的模式，包括通过失败链接可达的模式。
     * 
     * 此方法的时间复杂度为O(n)，其中n是Trie中的节点总数。
     * 必须在执行任何匹配操作前调用此方法，以确保算法的正确性。
     */
    private void buildFailureAndOutputLinks() {
        Queue<TrieNode> queue = new LinkedList<>();
        // 根节点的失败链接指向自身，表示匹配失败时回到初始状态
        root.setFailureLink(root);

        // 第一层节点（根节点的直接子节点）的失败链接都指向根节点
        // 这些节点加入队列，后续将处理它们的子节点
        for (TrieNode child : root.getChildren().values()) {
            child.setFailureLink(root);
            queue.add(child);
        }

        // 使用BFS遍历Trie树，为每个节点构建失败链接
        while (!queue.isEmpty()) {
            TrieNode current = queue.poll();
            for (Map.Entry<Character, TrieNode> entry : current.getChildren().entrySet()) {
                char c = entry.getKey();
                TrieNode child = entry.getValue();
                // 将当前处理的子节点加入队列，以便后续处理
                queue.add(child);

                // 查找当前节点的失败链接节点
                TrieNode failureNode = current.getFailureLink();
                // 如果失败节点没有与当前字符匹配的子节点，则沿着失败链接继续查找
                // 这是Aho-Corasick算法的核心部分，确保最长的后缀匹配
                while (failureNode != root && !failureNode.hasChild(c)) {
                    failureNode = failureNode.getFailureLink();
                }

                // 设置子节点的失败链接
                if (failureNode.hasChild(c)) {
                    // 如果找到了匹配的字符，失败链接指向该字符对应的节点
                    child.setFailureLink(failureNode.getChild(c));
                } else {
                    // 否则，失败链接指向根节点（重新开始匹配）
                    child.setFailureLink(root);
                }

                // 构建输出链接：继承失败链接节点的所有输出链接
                // 这确保了当到达某个节点时，可以识别所有可能的匹配
                child.addOutputLinks(child.getFailureLink().getOutputLinks());
                // 如果当前节点是单词结尾，将自身添加到输出链接中
                if (child.isEndOfWord()) {
                    child.addOutputLink(child);
                }
            }
        }
    }

    /**
     * 实际执行文本匹配的Aho-Corasick算法。
     * 此方法实现了Aho-Corasick算法的核心匹配逻辑，通过失败链接和输出链接高效地查找所有匹配项。
     * 对于每个匹配到的侵权词，会检查其是否适用于指定的站点，并将有效的匹配添加到结果列表中。
     * 如果是不区分大小写的Trie，会自动将输入文本中的字符转换为小写进行匹配。
     *
     * @param text 要检查的文本
     * @param site 当前的站点上下文
     * @param matches 用于存储匹配结果的列表
     */
    private void findMatchesInText(String text, String site, List<InfringingWordMatch> matches) {
        // 从根节点开始匹配
        TrieNode current = root;

        // 逐字符处理输入文本
        for (int i = 0; i < text.length(); i++) {
            char c = text.charAt(i);
            // 如果是不区分大小写的Trie，将字符转换为小写
            char charToFind = caseSensitive ? c : Character.toLowerCase(c);

            // 如果当前节点没有匹配的子节点，则沿着失败链接回溯
            // 这是Aho-Corasick算法的核心：当匹配失败时，不需要回到文本开头重新开始，
            // 而是跳转到可能的最长后缀匹配位置
            while (current != root && !current.hasChild(charToFind)) {
                current = current.getFailureLink();
            }

            // 尝试移动到下一个匹配节点
            if (current.hasChild(charToFind)) {
                current = current.getChild(charToFind);
            } else {
                // 如果根节点也没有匹配的子节点，则保持在根节点，继续处理下一个字符
                continue;
            }

            // 收集所有通过失败链接和输出链接找到的匹配项
            // 输出链接包含了所有在当前位置结束的模式
            for (TrieNode outputNode : current.getOutputLinks()) {
                InfringingWord word = outputNode.getInfringingWord();
                // 检查侵权词是否适用于当前站点
                if (isWordApplicableToSite(word, site)) {
                    // 计算匹配的起始位置：当前位置减去单词长度再加1
                    int position = i - word.getWord().length() + 1;
                    // 从原文中提取实际匹配的文本（可能与词库中的单词大小写不同）
                    String matchedText = text.substring(position, i + 1);
                    // 将匹配结果添加到列表中
                    addMatchToList(matches, matchedText, word, !caseSensitive, position);
                }
            }
        }
    }

    /**
     * 使用迭代方式将源Trie合并到目标Trie。
     * 使用迭代而非递归，避免大型Trie合并时可能的栈溢出问题。
     * 此方法使用广度优先遍历，通过队列管理待处理的节点对，确保所有节点都被正确合并。
     * 如果源节点是单词结尾，则相应的目标节点也会被标记为单词结尾，并继承源节点的侵权词信息。
     *
     * @param source 源Trie树的根节点
     * @param destination 目标Trie树的根节点
     */
    private void mergeTries(TrieNode source, TrieNode destination) {
        Queue<TrieNodePair> queue = new LinkedList<>();
        queue.add(new TrieNodePair(source, destination));

        while (!queue.isEmpty()) {
            TrieNodePair pair = queue.poll();
            TrieNode src = pair.source;
            TrieNode dest = pair.destination;

            for (Map.Entry<Character, TrieNode> entry : src.getChildren().entrySet()) {
                char c = entry.getKey();
                TrieNode sourceChild = entry.getValue();
                TrieNode destChild = dest.getOrCreateChild(c);

                if (sourceChild.isEndOfWord()) {
                    destChild.setEndOfWord(sourceChild.getInfringingWord());
                }

                queue.add(new TrieNodePair(sourceChild, destChild));
            }
        }
    }

    /**
     * 用于在迭代合并过程中存储源节点和目标节点对的辅助类。
     * 此类简化了Trie树合并过程中的节点对管理，避免使用递归方式可能导致的栈溢出问题。
     * 每个TrieNodePair实例包含一个源Trie节点和一个目标Trie节点，表示合并操作中的一对对应节点。
     */
    private static class TrieNodePair {
        /**
         * 源Trie树中的节点
         */
        final TrieNode source;

        /**
         * 目标Trie树中的节点，源节点的内容将被合并到这个节点
         */
        final TrieNode destination;

        /**
         * 创建一个新的节点对
         *
         * @param source 源Trie树中的节点
         * @param destination 目标Trie树中的节点
         */
        TrieNodePair(TrieNode source, TrieNode destination) {
            this.source = source;
            this.destination = destination;
        }
    }

    /**
     * 检查一个侵权词是否适用于给定的站点。
     * 如果侵权词的适用站点列表包含通配符"*"或者包含指定的站点，则返回true。
     * 如果站点参数为null，则只要侵权词有任何适用站点，就返回true。
     *
     * @param word 要检查的侵权词
     * @param site 当前的站点上下文，可以为null
     * @return 如果侵权词适用于给定站点则返回true，否则返回false
     */
    private boolean isWordApplicableToSite(InfringingWord word, String site) {
        if (word == null || word.getApplicableSites() == null || word.getApplicableSites().isEmpty()) {
            return false;
        }
        return site == null || word.getApplicableSites().contains("*") || word.getApplicableSites().contains(site);
    }

    /**
     * 将一个有效的匹配结果添加到列表中。
     * 使用Builder模式创建一个新的InfringingWordMatch对象，并将其添加到匹配结果列表中。
     *
     * @param matches 要添加到的匹配结果列表
     * @param matchedText 在文本中实际匹配到的原始文本
     * @param word 匹配的侵权词对象
     * @param isCaseInsensitive 是否是不区分大小写的匹配
     * @param position 匹配在原文中的起始位置
     */
    private void addMatchToList(List<InfringingWordMatch> matches, String matchedText, InfringingWord word, boolean isCaseInsensitive, int position) {
        matches.add(InfringingWordMatch.builder()
                .originalText(matchedText)
                .infringingWord(word.getWord())
                .applicableSites(word.getApplicableSites())
                .caseInsensitive(isCaseInsensitive)
                .position(position)
                .build());
    }
} 
